package main

import (
	"fmt"
	. "go_data_structures_and_algorithms/tool/pojo"
)

// 题解思路这道题第一组的逆序的尾节点是逆序完之后总的逆序链表的头节点所以要先行记录
// 还有就是要准备好翻转逆序的头尾位置并在上一组弄完后及时调整到下一组的位置上
// Start变量就是reverse逆序函数所需要的头指针，End变量就是reverse所需要的逆序函函数的尾指针
func reverseKGroup(head *Node1[int], k int) *Node1[int] {
	Start := head
	End := FindGroupEnd(head, k)
	if End == nil {
		return head
	}
	head = End
	reserve(Start, End)
	LastEnd := Start
	//因为reserve后上一组的尾结点连接着后面的链表，
	// 而且当后面一组的链表翻转的时候尾结点需要改变连接到下一组的End位置也就是下一组的头节点
	//所以需要记录一下上一组的尾节点
	for LastEnd.Next != nil {
		Start = LastEnd.Next         //因为上一组的尾结点连接着后面的链表所以它的next就是下一组start头指针的位置
		End = FindGroupEnd(Start, k) //返回这组对应的的尾结点
		if End == nil {              //如果尾结点不够数就直接返回head指针
			return head

		}
		reserve(Start, End) //逆序这一组的链表，提供头尾指针，头指针单纯用来提供数据，尾指针有两个作用
		//一个用来判断逆序操作有没有到头，再一个就是用来连接下一组链表，防止逆序完直接丢失后续节点
		LastEnd.Next = End
		//下一组逆序完后//end就变变成了下一组逆序好的链表的头部
		//start就变成了下一组逆序好的链表的尾部
		//如果不将LastEnd(上一组逆序完链表的尾部)的next原来指向此时的End(变成了这组链表的头)就会跳过这组链表
		//这时候再将LastEnd(上一组逆序完链表的尾部)的指向调整尾这一组逆序完链表的尾部
		LastEnd = Start
	}
	return head
}

func FindGroupEnd(head *Node1[int], len int) *Node1[int] {
	//假如一个链表要分成三个一组
	//头节点直接next两次就可以到达第三个节点所以len是多1的所以直接减去
	len--
	for len != 0 && head != nil { //只有当次数和head不等于nil都满足时for循环才会执行并不断获取head的下一个节点
		head = head.Next //当len==0时head达到了分成一组的尾结点，所以结束当前循环返回这个尾结点
		//当head==nil时就是剩下的节点不够凑成一组直接将head=nil返回外面判断为nil后直接结束程序
		len-- //因为不足k个不用逆序
	}
	return head
}
func reserve(start *Node1[int], end *Node1[int]) {
	end = end.Next //保存end的下一个节点因为end逆序后就会丢失
	var pre *Node1[int]
	cur := start         //保存头指针因为这个头指针逆序后就会变成尾指针还需要指向后面的链表的位置
	var next *Node1[int] //基本的逆序操作
	for cur != end {     //当cur==end时就是到头了end是下一组的节点
		next = cur.Next //逆序的基本操作1保留下一个节点的位置
		cur.Next = pre  //将前一个节点赋值尾当前节点的下一个节点
		pre = cur       //再讲pre指针后移
		cur = next      //将当前指针后移
	}
	start.Next = end //将其逆序完的start其实就是尾结点尾结点连接下一组链表的头节点让其连接起来
}

func main() {
	n1 := Node1[int]{Value: 1}
	n2 := Node1[int]{Value: 2}
	n3 := Node1[int]{Value: 3}
	n4 := Node1[int]{Value: 4}
	n5 := Node1[int]{Value: 5}
	n1.Next = &n2
	n2.Next = &n3
	n3.Next = &n4
	n4.Next = &n5
	Node1 := reverseKGroup(&n1, 2)
	fmt.Println(Node1)
}
